import java.util.Arrays;

public class FindTargetSumWays {

    public int findTargetSumWays1(int[] nums, int target) {
        int sum = 0;
        int n = nums.length;
        for (int i = 0; i < nums.length; i++) {
            sum += nums[i];
        }
        int flag = sum + target;
        if (flag % 2 != 0 || sum < target || flag < 0) return 0;
        int[][] dp = new int[n + 1][flag / 2 + 1];
        dp[n][0] = 1;
        for (int i = n - 1; i >= 0; i--) {
            for (int j = 0; j <= flag / 2; j++) {
                if (j - nums[i] >= 0) {
                    dp[i][j] = dp[i + 1][j] + dp[i + 1][j - nums[i]];
                } else dp[i][j] = dp[i + 1][j];
            }
        }
        return dp[0][flag / 2];
    }

    public int process(int[] nums, int i, int target) {
        if (i == nums.length) {
            return target == 0 ? 1 : 0;
        }
        return process(nums, i + 1, target - nums[i]) + process(nums, i + 1, target + nums[i]);
    }

    public int findTargetSumWays2(int[] nums, int target) {
        int sum = Arrays.stream(nums).sum();
        int n = nums.length;
        int delta = Math.max(Math.abs(target), sum);
        int[][] dp = new int[n + 1][Math.max(target + delta, sum + delta) + 1];
        dp[0][delta] = 1;
        for (int i = 0; i < n; i++) {
            for (int j = 0; j < dp[0].length; j++) {
                dp[i + 1][j] += j + nums[i] >= dp[0].length ? 0 : dp[i][j + nums[i]];
                dp[i + 1][j] += j - nums[i] >= 0 ? dp[i][j - nums[i]] : 0;
            }
        }
        return dp[n][target + delta];
    }

    public static void main(String[] args) {
        int[] nums = {1,1,1,1,1};
        System.out.println(new FindTargetSumWays().findTargetSumWays(nums, 3));
    }

    public int findTargetSumWays(int[] nums, int target) {
        int sum = Arrays.stream(nums).sum();
        if ((sum + target) % 2 != 0) return 0;
        target = (sum + target) / 2;
        if (target < 0) return 0;
        int[] dp = new int[target + 1];
        dp[0] = 1;
        for (int num : nums) {
            for (int i = target; i >= num; i--) {
                dp[i] += dp[i - num];
            }
        }
        return dp[target];
    }
}